package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _18_查找两个节点的最近公共父节点 {

    /**
     *  查找两节点的最近公共parent节点
     *
     *  1.
     *
     */
    public static TreeNode findCommonParent(TreeNode root, TreeNode t1, TreeNode t2) {

        if (root == null) {
            return null;
        }

        if (root == t1 || root == t2) {

            return root;
        }

        TreeNode left = findCommonParent(root.left, t1, t2);
        TreeNode right = findCommonParent(root.right,t1, t2);

        if (left != null && right != null) {

            return root;
        }

        return left != null ? left:right;
    }

    public static void main(String[] args) {

        /**
         *                  6
         *
         *               3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.right = new TreeNode(10);

        System.out.println(findCommonParent(t1, t1.right.left, t1.left.right));

    }
}
